package com.beney.ds.sorting;

import com.beney.ds.sorting.abs.AbstractSort;

public class ShellSort extends AbstractSort {
    private ShellSort() {
    }

    public static void sort(Comparable[] arr) {
        if (arr == null) return;
        int len = arr.length;
        for (int incr = len / 2; incr > 0; incr /= 2) {  // 组内步长
            for (int g = 0; g < incr; ++g) {  // 组号/每一组的第一个元素
                for (int i = g; i < len; i += incr) { // 组内插入排序
                    for (int j = i; j > g && isLess(arr, j, j - incr); j -= incr) {
                        swap(arr, j, j - incr);
                    }
                }
            }
        }
    }

    public static void sortX(Comparable[] arr) {
        if (arr == null) return;
        int len = arr.length, now, pre;
        for (int incr = len / 2; incr > 0; incr /= 2) {
            for (int i = 0; i < len; ++i) { // 遇到的元素在哪个组就在哪个组内插入排序
                now = i;
                while ((pre = now - incr) > 0 && isLess(arr, now, pre)) {
                    swap(arr, now, pre);
                    now = pre;
                }
            }
        }
    }
}
